package com.wjy.Data_Structure.recursion;

public class recursion {
	/**
	 * 计算n!
	 * @param n
	 * @return
	 */
	public int factorial(int n) {
		if (n == 0)
			return 1;
		else
			return n * factorial(n - 1);

	}

	/**时间复杂度为 Θ(n)
	 * 计算以 x 为底的 n 次幂，其中 n 为非负整数
	 * @param x
	 * @param n
	 * @return
	 */
	public int power(int x, int n) {
		if (n == 0)
			return 1;
		else
			return x * power(x, n - 1);
	}

	/**
	 * 计算以 x 为底的 n 次幂，其中 n 为非负整数 时间复杂度为 Θ(log n)。 
	 * @param x
	 * @param n
	 * @return
	 */
	public int power1(int x, int n) {
		int y;
		if (n == 0) {
			y = 1;
		} else {
			y = power1(x, n / 2);
			y = y * y;
			if (n % 2 == 1)
				y = y * x;
		}
		return y;
	}

	/**
	 * 要求将塔座 X 上的所有盘子移动到塔座 Z 上 并保持原来的顺序
	 * @param n
	 * @param x
	 * @param y
	 * @param z
	 */
	public void hanio(int n, char x, char y, char z) {
		if (n == 1) {
			move(x, n, z);
		} else {
			hanio(n - 1, x, z, y);
			move(x, n, z);
			hanio(n - 1, y, x, z);
		}

	}

	private void move(char x, int n, char y) {
		System.out.println("Move " + n + " from " + x + " to " + y);
	}

	public void coding(int[] b, int n) {
		if (n == 0) {
			b[n] = 0;
			outBn(b);
			b[n] = 1;
			outBn(b);
		} else {
			b[n] = 0;
			coding(b, n - 1);
			b[n] = 1;
			coding(b, n - 1);
		}
	}

	private void outBn(int[] b) {
		for (int i = 0; i < b.length; i++)
			System.out.print(b[i]);
		System.out.println();
	}
}
